package com.mdnote.practice.sort;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/22 20:42
 * @Email rhythm_2019@163.com
 * @Description 242. 有效的字母异位词
 */
public class LeetCode242 {

    public boolean isAnagram(String s, String t) {
        // Sort
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        quickSort(sChars, 0, sChars.length - 1);
        quickSort(tChars, 0, tChars.length - 1);

        return (new String(sChars)).equals(new String(tChars));
    }

    private void quickSort(char[] chars, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivot = partition(chars, start, end);
        quickSort(chars, start, pivot - 1);
        quickSort(chars, pivot + 1, end);

    }

    private int partition(char[] chars, int start, int end) {
        int pivot = end, counter = start;
        for (int i = start; i < end; i++) {
            if (chars[i] < chars[pivot]) {
                char tmp = chars[i]; chars[i] = chars[counter]; chars[counter] = tmp;
                counter++;
            }
        }
        char tmp = chars[pivot]; chars[pivot] = chars[counter]; chars[counter] = tmp;

        return counter;
    }

    @Test
    public void test_01() {
        LeetCode242 leetCode242 = new LeetCode242();
        Assert.assertEquals(true, leetCode242.isAnagram("cat", "tac"));
        Assert.assertEquals(false, leetCode242.isAnagram("eat", "tac"));
        Assert.assertEquals(false, leetCode242.isAnagram("", "tac"));
        Assert.assertEquals(true, leetCode242.isAnagram("", ""));
        Assert.assertEquals(false, leetCode242.isAnagram("ab", "a"));
    }
}
